package graph;



/**
 * @Author Zhouchb
 * @Create 2021-10-2021/10/30 :11:12
 * @Description
 */
class DepthFirstSearchTest{
    public static void main(String[] args) {
        Graph graph = new Graph(13);
        graph.addEdge(0,5);
        graph.addEdge(0,1);
        graph.addEdge(0,2);
        graph.addEdge(0,6);
        graph.addEdge(5,3);
        graph.addEdge(3,4);
        graph.addEdge(4,6);

        graph.addEdge(7,8);

        graph.addEdge(9,11);
        graph.addEdge(9,10);
        graph.addEdge(9,12);
        graph.addEdge(11,12);

        DepthFirstSearch firstSearch = new DepthFirstSearch(graph,0);

        System.out.println("测试与某个顶点统统的顶点数量："+firstSearch.count());
        System.out.println("判断0与4是否相通："+firstSearch.marked(4));
        System.out.println("判断0与7是否相通："+firstSearch.marked(7));
    }
}
public class DepthFirstSearch {
    //索引代表顶点，值表示当前顶点是否已经被搜索
    private boolean[] marked;
    //记录有多少个顶点与s顶点相通
    private int count;

    //构造深度优先搜索对象，使用深度优先搜索找出个g图中与s顶点相通顶点
    public DepthFirstSearch(Graph graph, int s) {
        //初始化marked数组
        marked = new boolean[graph.v()];
        //初始化跟顶点s相通的顶点的数量
        this.count = 0;
        dfs(graph,s);
    }

    //使用深度优先搜索找出G图中v顶点的所有相通顶点
    private void dfs(Graph graph, int v) {
        marked[v] = true;
        for (Integer w : graph.adj(v)) {
            if (!marked[w]){
                dfs(graph,w);
            }
        }
        //相通顶点数量加1
        count++;
    }

    //判断w顶点与s顶点是否相通
    public boolean marked(int w) {
        return this.marked[w];
    }

    //获取与顶点s相通的所有顶点的总数
    public int count() {
        return count;
    }
}
